1. Technical Field
This invention relates in general to caches in computer systems and more particularly, but not exclusively, to a method for replacing blocks in the cache.
2. Background Art
Caches provide comparatively close, fast access to important information for processing resources of a computer. For example, caches are often used to store memory blocks that have been accessed recently by a central processing unit (CPU). But it is not practical to make caches large enough to store all of the available memory blocks. Aside from the obvious fact that such a large cache would make the main memory unnecessary, cache memory is more expensive than main memory. To keep costs down, caches tend to be of smaller size relative to main memory.
Because caches cannot store every block in main memory, when a new block needs to be allocated from the cache, the cache must use a replacement policy to decide what block currently in the cache is to be replaced. A good replacement policy is highly valuable for effective cache utilization. A Least Frequently Used (LFU) replacement policy tracks how often each block in the cache has been used and replaces the block that has the lowest frequency of use. A Least Recently Used (LRU) replacement policy tracks how long it has been since each block in the cache has been used and replaces the block that has gone the longest since it was last used. LRU and LFU are two popular cache replacement policies. However, neither LRU nor LFU suits the requirements of all computing applications. As the size and speed of memory systems grow with successive generations of integrated circuit technology, the performance of such memory systems is increasingly sensitive to inefficiencies in cache management.